from collections import deque
from typing import Optional

from python.mypackage.TreeNode import TreeNode


class Solution:
    """
     方法： 使用广度优先搜索计算二叉树每层的平均值
     
     Args:
         root: Optional[TreeNode] - 二叉树的根节点
     
     Returns:
         List[float]: 包含每层节点平均值的列表
     
     Time: O(n) - 其中n是二叉树的节点数，每个节点只被访问一次
     
     Space: O(w) - 其中w是二叉树的最大宽度，队列中最多存储一层的所有节点
     """
    def averageOfLevels(self, root: Optional[TreeNode]) -> List[float]:
        ans = []
        q = deque([root])
        while q:
            length = len(q)
            sum = 0
            for _ in range(length):
                node = q.popleft()
                sum += node.val
                if node.left:
                    q.append(node.left)
                if node.right:
                    q.append(node.right)
            ans.append(sum / length)
        return ans